package org.magi.others;

import java.util.*;

public class LRU <K, V> {

    private static class DLinkedNode<K, V> {
        DLinkedNode<K, V> pre;
        DLinkedNode<K, V> next;
        K key;
        V value;

        DLinkedNode(K key, V val) {
            this.key = key;
            this.value = val;
        }
    }
    private final Map<K, DLinkedNode<K, V>> cache;

    private final DLinkedNode<K, V> HEAD = new DLinkedNode<>(null, null);
    private final int MAX_SIZE;

    public LRU(int size) {
        MAX_SIZE = Math.max(1, size);
        cache = new HashMap<>(MAX_SIZE);
        HEAD.next = HEAD;
        HEAD.pre = HEAD;
    }

    public V get(K key) {
        DLinkedNode<K, V> o = cache.get(key);
        if (o != null) {
            cacheHit(o);
            return o.value;
        }
        return null;
    }

    private void cacheHit(DLinkedNode<K, V> target) {
        if (HEAD.next != target) {
            target.pre.next = target.next;
            target.next.pre = target.pre;
            target.next = HEAD.next;
            target.pre = HEAD;
            HEAD.next = target;
        }
    }

    private void eliminate() {
        DLinkedNode<K, V> target = HEAD.pre;
        target.pre.next = HEAD;
        HEAD.pre = target.pre;
        target.pre = null;
        target.next = null;
        cache.remove(target.key);
    }

    public void put(K key, V val) {
        DLinkedNode<K, V> node = cache.get(key);
        if (node != null) {
            node.value = val;
            return;
        }
        DLinkedNode<K, V> target = new DLinkedNode<>(key, val);
        if (cache.size() == MAX_SIZE) {
            eliminate();
        }
        target.pre = HEAD;
        target.next = HEAD.next;
        HEAD.next.pre = target;
        HEAD.next = target;
        cache.put(key, target);
    }
}
